/**
 * @program: LoveDataStructures1
 * @description: 斐波那契
 * @author: wxc
 * @create: 2021-04-03 13:19
 **/
public class Main {
    public static int getFibonacci(int number,int x0,int x1) {
        int temp = x1;
        x1 = x0 + x1;
        x0 = temp;
        if (number == 2) return x1;
        return getFibonacci(number-1,x0,x1);
    }
    // O(2^n)
    public static int getFibonacci(int number) {
        if (number <= 1) return number;
        return getFibonacci(number - 1) + getFibonacci(number - 2);
    }

    public static int getFibonacci2(int number) {
        if (number <= 1) return number;
        int x1 = 0;
        int x2 = 1;
        for (int i = 0; i < number - 1; i++) {
            int sum = x1 + x2;
            x1 = x2;
            x2 = sum;
        }
        return x2;
    }


    public static void main(String[] args) {
//        System.out.println(getFibonacci(5, 0, 1));
//        System.out.println(getFibonacci(64));
        System.out.println(getFibonacci2(64));
    }
}
